import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class 队列的最大值 {

    private static class MaxQueue {
        Queue<Integer> queue;
        Deque<Integer> deque;

        public MaxQueue() {
            queue = new LinkedList<Integer>();
            deque = new LinkedList<Integer>();
        }

        public int max_value() {
            if (deque.isEmpty()) {
                return -1;
            }
            return deque.peekFirst();
        }

        public void push_back(int value) {
            while (!deque.isEmpty() && deque.peekLast() < value) {
                deque.pollLast();
            }
            deque.offerLast(value);
            queue.offer(value);
        }

        public int pop_front() {
            if (queue.isEmpty()) {
                return -1;
            }
            int ans = queue.poll();
            if (ans == deque.peekFirst()) {
                deque.pollFirst();
            }
            return ans;
        }

        public static void main(String[] args) {
            MaxQueue maxQueue = new MaxQueue();
            maxQueue.push_back(1);
            maxQueue.push_back(4);
            maxQueue.push_back(2);
            maxQueue.push_back(1);
            maxQueue.push_back(1);
            int i = maxQueue.pop_front();
            System.out.println(i);
            System.out.println(maxQueue.max_value());
        }
    }
    public int[] spiralOrder(int[][] matrix) {
        //上边界
        int top=0;
        //下边界
        int bottom=matrix.length-1;
        //左边界
        int left=0;
        //右边界
        int right=matrix[0].length-1;
        int []array=new int[(right+1)*(bottom+1)];
        int c=0;
        while(true){
            //从左到右
            for (int i = left; i <= right; i++) {
                array[c++]=matrix[top][i];
            }
            top++;
            //从上到下
            for (int i = top; i <= bottom; i++) {
                array[c++]=matrix[i][right];
            }
            right--;
            //从右到左
            for (int i = right; i >=left;i--) {
                array[c++]=matrix[bottom][i];
            }
            bottom--;
            //从下到上
            for (int i = bottom; i >= top;i--) {
                array[c++]=matrix[i][left];
            }
            left++;
        }
    }
}

class Test11{
    public static void main(String[] args) {
        System.out.println(firstUniqChar1("aadadaad"));
    }

    public static int lengthOfLongestSubstring(String s) {
        //if(s==null) return 0;这句话可以不加，s.length()长度为0时，不进入下面的循环，会直接返回max=0;
        //划定当前窗口的坐标为(start,i],左开右闭,所以start的初始值为-1，而非0。
        int max = 0,start =-1;
        //使用哈希表map统计各字符最后一次出现的索引位置
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i=0;i<s.length();i++){
            char tmp = s.charAt(i);
            //当字符在map中已经存储时，需要判断其索引值index和当前窗口start的大小以确定是否需要对start进行更新:
            //当index>start时，start更新为当前的index,否则保持不变。
            //注意若index作为新的start，计算当前滑动空间的长度时也是不计入的，左开右闭，右侧s[i]会计入，这样也是防止字符的重复计入。
            if(map.containsKey(tmp)){
                start = Math.max(start,map.get(tmp));
            }
            //如果map中不含tmp，此处是在map中新增一个键值对，否则是对原有的键值对进行更新
            map.put(tmp,i);
            //i-start,为当前滑动空间(start,i]的长度，若其大于max，则需要进行更新。
            max = Math.max(max,i-start);
        }
        return max;
    }
    public static char firstUniqChar1(String s) {
        HashMap<Character, Boolean> dic = new HashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        for(char c : sc)
            if(dic.get(c)) return c;
        return ' ';
    }

    public static char firstUniqChar(String s) {
        /**
         构建一个HashMap
         **/
        char []c=s.toCharArray();
        Map<Character,Boolean> map = new HashMap();
        for (int i = 0; i < c.length; i++) {
            map.put(c[i], !map.containsKey(c));
        }
        for (int i = 0; i < c.length; i++) {
            if(!map.get(c[i])){
                return c[i];
            }
        }
        return ' ';
    }
}
